import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/10 20:54
 * @description 当只有两个气球的时候，要想获得更多的硬币，需要先锤掉数值小的，后锤掉大的，当 n > 2, 先将中间 n-2个气球，挑选最小的锤掉，最后锤大的，大的留在后面贡献更大
 * 贪心思路, 无法AC
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {9, 76, 64, 21};
        System.out.println(solution.maxCoins(nums));
    }
    public int maxCoins(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        // 放置[下标，值]
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i, nums[i]);
        }
        // 中间下标的小顶堆[i, nums[i]]
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)-> a[1] - b[1]);
        for (int i = 1; i < n -1; i++) {
            pq.add(new int[] {i, nums[i]});
        }
        int ans = 0;
        while (!pq.isEmpty()) {
            int[] temp = pq.poll();
            int left = map.lowerKey(temp[0]), right = map.higherKey(temp[0]) ;
            ans += temp[1] * map.get(left) * map.get(right);
            map.remove(temp[0]);
        }
        return ans + nums[0] * nums[n-1] + Math.max(nums[0], nums[n-1]);
    }
}
